/**
 * [31] 下一个排列
 * tips:
 * # 1 <= nums.length <= 100
 * # 0 <= nums[i] <= 100
 * 瞪眼法：
 * # 最小排列：1234
 * # 1234 # 1243 # 1324 # 1342 # 1423 # 1432
 * # 2134 # 2143 # 2314 # 2341 # 2413 # 2431
 * # 3124 # 3142 # 3214 # 3241 # 3412 # 3421
 * # 4123 # 4132 # 4213 # 4231 # 4312 # 4321
 * # 最大排列：4321
 * 思路：
 * # 升序最小，降序最大
 * # 保证改动最小：因为右边位的权重小，所以从右往左使变大的幅度最小 => 下一个排列
 * # 1. 从右往左，找到第一个降序的位置，从该位置往后为子排列（已是最大），往前一个数为待替换位
 * # 2. 从子排列中找出刚好大于待替换位的数与之交换
 * # 3. 将子排列调整为升序
 *
 * @format
 * @lc app=leetcode.cn id=31 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */

var nextPermutation = function (nums) {
    // nums.swap = function (a, b) {
    //     if (a === b) return false
    //     this[a] += this[b]
    //     this[b] = this[a] - this[b]
    //     this[a] -= this[b]
    // }
    const END = nums.length - 1
    let [i, j] = [END, END]
    // 确定子序列：nums[i,n-1]
    for (; i > 0; i--) if (nums[i] > nums[i - 1]) break
    // 交换进位：刚好大于 nums[i-1]
    if (i > 0) {
        for (; j > 0; j--) if (nums[j] > nums[i - 1]) break
        ;[nums[i - 1], nums[j]] = [nums[j], nums[i - 1]]
    }
    // 翻转子序列
    // const MID = Math.floor((END + i) / 2)
    j = END
    while (i < j) {
        ;[nums[i], nums[j]] = [nums[j], nums[i]]
        i++, j--
    }
}
// debugger
// const nums = [1, 2, 3]
// nextPermutation(nums)
// console.log(nums)
// @lc code=end

// Accepted
// 266/266 cases passed (55 ms)
// Your runtime beats 96.51 % of javascript submissions
// Your memory usage beats 5.08 % of javascript submissions (51.2 MB)
